В рамках серии статей по применению математической оптимизации для решения задач в бизнесе мне хотелось бы кратко, но ёмко раскрыть причины и предпосылки возникновения потребности у бизнеса решений задач такого класса, а также привести конкретные примеры кейсов, которые успешно реализованы в крупнейших компаниях мира. В отдельности каждый кейс заслуживает не менее 50 страниц текста для полноценного описания, я же постараюсь изложить главную суть решений и некоторые технические особенности в формате статей на Хабре.

Алгоритмы математической оптимизации относятся к категории Prescriptive – аналитики, наиболее сложного и ценного для бизнеса аналитического сегмента. Данная категория позволяет создавать сложные интеллектуальные системы принятия решения с целью максимизировать экономические, производственные и многие другие KPI в рамках заданных ограничений.  Математическая оптимизация имеет своё применение в каждом из видов бизнеса любого масштаба, включая промышленность, производство, розничную торговлю, транспорт и логистика, телеком, агросектор, энергетика, строительство, финансы, банкинг, спорт, кино, медицина, образование и т.д. В текущей статье пойдет речь о задачах в индустрии пассажирских авиалиний.

Почему начинаем с пассажирских авиалиний? Главная причина: это одна из самых подходящих индустрий для генерации экономического эффекта за счет применения оптимизационных решений. К примеру, компания Lufthansa своим решением NetLine/FleetAssigner для планирования расписаний оценивает эффект от внедрения в 600 000 евро для средней компании. Также на текущий момент для крупных игроков мирового рынка решение подобных задач является актуальным, о чем может говорить большое количество пресс-релизов и вакансий на позицию Operations Research Scientist.

Компании, занимающие лидирующие позиции в авиационном секторе, имеют собственный штат специалистов по математической оптимизации (эксперты по исследованию операций / консультанты по оптимизации), либо привлекают партнерские ресурсы на разработку и поддержку решений, тем самым получают конкурентное преимущество. Наличие экспертизы в этом направлении на текущий момент является обязательным для крупнейших компаний в секторе.

Но зачем компаниям иметь свой собственный штат специалистов узкого профиля? На рынке присутствует некоторое количество коробочных решений, которые решают отдельные задачи с применением оптимизационных алгоритмов, в том числе те, о которых пойдет разговор далее в статье, но несмотря на это спустя некоторое время компании пришли к выводу, что разработка решений специально для компании имеет серьезные преимущества перед готовыми решениями:

• Учет всех особенностей процессов конкретной компании. В каждой из компаний многие процессы выстроены с учетом внутренних особенностей ведения бизнеса, законодательства, рыночной конъюнктуры и готовое решение может быть в полной степени использовано, только если учтены все эти нюансы.

• Возможность гибкой и оперативной модификации с учетом пожеланий специалистов компании по удобству использования. Бизнес не стоит на месте и находится в режиме постоянных изменений, что требует постоянного вовлечения экспертов.

• Возможность решений некоторых задач для непредвиденных для системы случаев в максимально короткие сроки. Благодаря наличию экспертов можно в ручном режиме задать условия возникшей задачи и получить её решение.

• Возможность гибкой интеграции решения в существующую архитектуру. Благодаря разработке продукта ин-хаус, есть возможность учесть все интеграционные взаимодействия, настроить потоки без лишних нагромождений и костылей.

Наиболее важными задачами с точки зрения экономической эффективности в авиалиниях являются 3 задачи с применением математической оптимизации:

• Планирование маршрутов и расписаний для максимизации прибыли и использования флота

• Планирование экипажей на рейсы с учетом нормативных требований и обеспечения квалификации

• Динамическое ценообразование на базе истории с учетом кросс-эффектов альтернативных вариантов

Далее я постараюсь изложить суть каждого из кейсов.

Кейс 1. Планирование маршрутов и расписаний для максимизации прибыли и использования флота

Основная цель решения — построение наилучшего расписания с точки зрения экономической эффективности, включая распределение определенных самолетов на определенные рейсы. Благодаря эффективному использованию алгоритмов математической оптимизации и машинного обучения становится возможным создать инструмент для поиска наилучшего способа использования существующих возможностей компании.

При выборе оптимального расписания учитываются следующие факторы:

• Прогнозируемый спрос на авиабилеты на различные варианты расписания с учетом влияния наличия альтернативных рейсов как внутри компании, так и среди конкурентов. Для построения максимально точного прогноза спроса необходимо учитывать все факторы, для различных направлений факторы могут быть различными. Важно в полной степени обеспечить наличие полноты данных для выполнения этого этапа, иначе качество решения в значительной степени будет не приемлемым для принятия ключевых решений.

• Показатели доходов и расходов по рейсам. Необходимо учитывать расходы не только на выполнение рейса, но и расходы на содержание транспорта и экипажей в командировках. Доходная составляющая зависит от прогнозируемого спроса, стоимость билета при этом выражается через прогрессивную шкалу без учета динамического ценообразования.

• Ограничения по ресурсам: количество и вместимость самолетов, персонал, время обслуживания, обучения и т.д. Важно учитывать, чтобы хватало людей, способных обеспечить выполнение рейсов по квалификационным требованиям. Чтобы было время на выполнение работ по подготовке транспорта и время на обслуживание.

• Ограничения инфраструктуры аэропорта, законодательные, условия договоров на выполнение полетов различных направлениях, нормативы по возможным задержкам и прочие нормативные ограничения.

В рамках построения интегрированного решения прогнозы спроса (и как следствие, доходов) обычно строятся заранее с использованием машинного обучения, прежде чем запускать задачу оптимизации. Выбор прогнозов спроса в модели оптимизации учитывает кросс-эффекты влияния рейсов внутри компании, а также наличие и отсутствие альтернатив у других игроков рынка. Оптимизационная модель как правило относится к классу смешанного целочисленного программирования (в меньшей достоверности можно пробовать решать нелинейную задачу), при этом кросс-эффекты в этой задаче моделируются в задаче с помощью комплексных индексов и вспомогательных переменных. В самой задаче используется общая прибыль на уровне подзадачи взаимосвязанных рейсов на базе примененной прогрессивной шкалой стоимости для каждого из рейсов для расчета дохода и расхода, который в теории может быть различным для одного и того же рейса, но в разное время.

Сама задача при нагромождении большим количеством опций, ограничений и высокой детализации становится комбинаторно сложной. Несмотря на отсутствие необходимости построения плана очень часто для работы с большим количеством сценариев у крупных компаний вопрос времени поиска стоит остро и для решения требуется качественная модель с хорошей линейной релаксацией и топовый коммерческий солвер.

Кейс 2. Планирование экипажей на рейсы с учетом нормативных требований и обеспечения квалификации

Главная цель решения – минимизация затрат на персонал. При модели вознаграждения за время работы, оно позволяет напрямую сократить расходы за счет меньшего использования определенных людей. При модели фиксированного вознаграждения – сократить численность персонала, увеличивая производительность труда. Решение предназначено для поиска оптимальной конфигурации экипажа для запросов на полеты с учетом:

• Предоставление квалификации — умение работать с определенным транспортным средством, знание языка, опыт, способности, разрешения на нахождение в стране и т.д. Важно обеспечить каждый рейс пилотами, которые обучены работе с определенной моделью самолета, обеспечить бортпроводников со знанием определенного языка для проведения международных рейсов и т.д. Также требуется балансировка состава по опыту работы для того, чтобы на борту всегда часть сотрудников была зрелой с точки зрения выполненных полетов в определенных направлениях.

• Соблюдение трудового законодательства и правил внутреннего трудового распорядка. В рамках планирования выполнения рейсов необходимо учитывать нормы по продолжительности рабочего дня, количество возможных перелетов за определенный период и т.д.

• Удовлетворение личных предпочтений и потребностей членов экипажа. В некоторых случаях учитываются предпочтения членов экипажей, как по наличию в них других сотрудников, так и по определенным направлениям.

• Другие бизнес-ограничения и предложения

В классическом изложении задача планирования экипажа относится к классу задач смешанного целочисленного программирования. Переменные определяют, какой конкретный сотрудник закреплен за определенным рейсом, целевая функция — общие затраты, а ограничения — выражения требований к персоналу и процессу.

Планировщик должен уметь адаптироваться к внезапным изменениям – задержкам или отменам рейсов, отсутствию членов экипажа и т. д. Поэтому в этом случае время поиска решения очень критично, что, в свою очередь, указывает на важность построения хорошей